package leetcode_600;

import java.util.LinkedList;
import java.util.Queue;

/**
 *@author 周杨
 *Matrix01_542 给定一个int的二维数组 里面只有0和1 返回这个矩阵 每个元素表示附近最近的0的距离
 *describe:广度优先遍历 +动态规划 AC 72%
 *2018年9月12日 上午10:50:16
 */
public class Matrix01_542 {
	
	 /**
	 * describe:广度优先遍历 +动态规划 
	 * 2018年9月12日 上午11:01:14
	 */
	public int[][] updateMatrix(int[][] matrix) {
	       int[] dx = new int[]{-1, 0, 1, 0};
	        int[] dy = new int[]{0, 1, 0, -1};
	        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return matrix;
	        int m = matrix.length;
	        int n = matrix[0].length;
	        int[][] dp = new int[m][n];
	        Queue<int[]> q = new LinkedList<>();
	        for (int i = 0; i < m; i++) {
	            for (int j = 0; j < n; j++) {
	                if (matrix[i][j] != 0) dp[i][j] = -1;
	                else q.add(new int[]{i, j});
	            }
	        }
	        while(!q.isEmpty()) {
	            int[] curr = q.poll();
	            int x = curr[0], y = curr[1];
	            for (int i = 0; i < 4; i++) {
	                int _x = x + dx[i];
	                int _y = y + dy[i];
	                if (_x < 0 || _y < 0 || _x >= m || _y >= n || dp[_x][_y] != -1) {
	                    continue;
	                }
	                dp[_x][_y] = dp[x][y] + 1;
	                q.add(new int[]{_x, _y});
	            }
	        }
	        return dp;
	    }
	
	/**
	 * describe:用动态规划的思想解决 思想错误 因为先后遍历顺序决定了状态转移方程的状态  
	 * 2018年9月12日 上午10:59:02
	 */
	public int[][] updateMatrix1(int[][] matrix) {
        for(int i=0;i<matrix.length;++i)
        	for(int j=0;j<matrix[0].length;++j) {
        		if(matrix[i][j]!=0) {
        			int min=matrix[i][j];
        			if(i-1>=0)
        				min=Math.min(min, matrix[i-1][j]);
        			if(i+1<matrix.length)
        				min=Math.min(min, matrix[i+1][j]);
        			if(j-1>=0)
        				min=Math.min(min, matrix[i][j-1]);
        			if(j+1<matrix[0].length)
        				min=Math.min(min, matrix[i][j+1]);
        			matrix[i][j]=min+1;
        		}
        	}
        return matrix;
    }
	
	
}
